Computers and data terminals operate on information in digital form. The process of converting information into its binary equivalent is called "coding" or "encoding". A decimal number can be coded as a pure binary number or with a code based upon the binary number system. In the pure binary code, every decimal number is translated to its equivalent in the binary number system. Perhaps the most widely used code for converting decimal numbers to binary form is the binary coded decimal (BCD) code. The BCD code combines some of the characteristics of both the binary and decimal number systems. The BCD code is a system of representing the decimal digits zero through nine with a four-bit pure binary word. The BCD code uses the standard 8421 position weighting system of the pure binary code. As with the pure binary code, a BCD number can be converted into its decimal equivalent by simply adding together the weights of the bit positions where binary ones occur. To represent a decimal number in BCD notation, the appropriate four-bit code is substituted for each decimal digit. For example, the decimal integer 83 in BCD is 1000 0011.
Another well-known coding scheme is the ASCII code (American Standard Code for Information Interchange). This is a special binary-based code widely used in microprocessors and data communications equipment, especially in transferring data between microprocessors and peripheral devices. ASCII is a seven-bit code and therefore can represent 2.sup.7 =128 different characters. The upper and lower case alphabet, various mathematical and textual symbols, and special computer commands are assigned specific bit representations in the ASCII code.
Another widely-used code for coding digital numbers is the Gray code. The Gray code is a non-weighted code system, and is also a cyclic code. A cyclic code is one in which any code word can be shifted one bit left or right, and the result will always be another valid code word. Each left shift or right shift produces a legitimate code word representing a different symbol. Note that cyclic codes are a subclass of linear codes; that is, all cyclic codes are linear codes, but the converse is not true. Another characteristic of the Gray code is that there is a change in only one bit from one code word to the next one in sequence. Thus, the Gray code permits code circuitry to operate at higher speeds with fewer errors. The disadvantage of the Gray Code is its inapplicability to arithmetic computations. To perform arithmetic operations, a number coded with the Gray code must be converted into pure binary form. Further information regarding the Gray code can he found in the Electronic's Engineer's Handbook, Second Edition, by Donald G. Fink and Donald Christiansen, 1982 at page 23-20.
The coding schemes discussed above are typically used to encode letters, numbers, and symbols by various configurations of binary one's and zero's. These codes do not contain features that ensure data integrity in a computer system or network of data terminals. Internal and external data transmissions within and between computers and data terminals occurs continuously and at high speed. Imperfections in the transmission channels and failures within the communicating devices inevitably produce some erroneous data, and it is therefore desirable to detect and correct such errors whenever they occur. The basic premise for error detection and correction is to design a code in which each word contains more bits than are needed to represent all the symbols in the data set, i.e., more bits than are necessary to simply transmit the information. The extra bits provide information for error correcting and/or detecting. If a received bit sequence is not among those assigned to data or information symbols, an error is known to have occurred.
One such commonly used error-detection code is the parity check. Assume that eight bits are used to represent data and an additional bit is reserved as a check bit. A simple electronic circuit can determine whether an even or odd number of one bits is included in the eight bit positions. If odd parity is chosen, and there are an even number of one bits, a one bit can be inserted in the check-bit position. If an odd number of one bits exist, a zero is placed in the check position. As a result, all transmitted code words will have an odd number of one bits. If the received nine-bit sequence contains an even number of one bits, an error occurred. There are limitations in the use of the simple parity scheme as a mechanism for error detection, since in many transmission channels and storage systems there is a tendency for a failure to produce simultaneous bit errors in two adjacent positions. This type of error would not be detected since the parity of the word remains unchanged. Also, the parity scheme does not provide error correction.
Any data stream can be coded with a linear code (for example, Reed-Solomon, BCH, Hamming, or general polynomial codes) to provide error detection and correction. This is accomplished by appending a check word to the data stream representing the information, i.e., the data word. To generate the check word a function G(x) is "divided" into the data word, the quotient is discarded, and the remainder forms the check word. In the subtract portion of the division operation, the remainder is obtained through an XOR (exclusive OR) operation rather than by legitimate subtraction. Therefore, any G(x) will "divide" into another number with an equal number of digits one time regardless of whether G(x) is larger or smaller than the dividend.
An example of this technique is illustrated below for a linear polynomial code using the binary system for the polynomial coefficients (symbols); this technique is well known in the coding art. Assume a generating polynomial EQU G(x)=x.sup.5 +x.sup.4 +x+1
and a data stream 10110111. The message polynomial formed by this data stream is: EQU M(x)=x.sup.7 +x.sup.5 +x.sup.4 +x.sup.2 +x+1
Note the most significant bit in M(x) is on the left. To produce the check word, M(x) is multiplied by the number of bits in the check word, which is the same as the highest order of G(x). The result is shown below. EQU x.sup.5 (x.sup.7 +x.sup.5 +x.sup.4 +x.sup.2 +x+1)=x.sup.12 +x.sup.10 +x.sup.9 +x.sup.7 +x.sup.6 +x.sup.5 =1 0 1 1 0 1 1 1 0 0 0 0 0
The result is divided by G(x). ##EQU1## The check word is appended to the message producing a transmitted bit stream of EQU 1 0 1 1 0 1 1 1 0 1 0 0 1
At the receiver the transmitted bit stream is "divided" by the same G(x), and if the remainder is zero there is no error in the received code word. ##EQU2##
The Hamming code is a well-known linear code. The Hamming code is also a forward error-correcting code, meaning that a device receiving information in Hamming code form has the capacity to detect and correct some errors in the received transmission. Hamming bits are bits placed anywhere in the string of informational bits, to allow the receiver to detect and correct a limited number of errors. Of course, use of the Hamming code for error detection and correction involves the transmission of additional bits, that is, bits in excess of those representing the information to be transmitted. Additional details regarding the Hamming code can be found in the Digital and Data Communications by Vincent F. Alisouskas and Wayne Tomasi, 1985 at pages 53-55.
One well-known application for the data codes discussed above is a data network, where several computers or data terminals, each located at a node of the network, are communicating with each other over the network. Typically, the information is transmitted in packets, each packet comprising one or more code words; each code word can range in length from a few bits to thousands of bits, depending on the application. Each code word may include an address header, a data word, and a check word. Noise on the network or within the communicating devices can distort bits in a transmitted word, causing the receiving device to interpret the word incorrectly. Thus the various error detecting and correcting techniques are used to provide reliable data communications over the network.
When the network is arranged in a ring fashion, it is necessary for a communicating device at a source node to communicate with a communicating device at a destination node via each intervening node in the ring. In such a communicating scheme each code word includes an address header indicating in some way, the communicating device for which the information is intended. For example, the address header may contain the address of the destination node. As the code word moves around the ring each communicating device checks the address header to determine if the information has reached its intended destination. If the information has not reached its destination it is transmitted farther along the ring. Generally, at each intervening node the code word is simply retransmitted without any change to its contents. In some applications, however, it may be desirable for an intervening node to change the code word before retransmission, for instance to signal an interrupt request. Alternatively, if a count representing the number of nodes to pass through before reaching the destination is placed in the address header, each node decrements the count and passes on the new header until the destination node is recognized by an all-zero header. These addressing schemes are both well-known techniques for communicating data within a ring network.
In the latter communication scheme where the address is changed at each node, the check-word scheme discussed above cannot be used because when a communicating device receives an information signal and changes the address portion thereof for transmission to the next device in the ring, the check word looses its validity. Once the code word (i.e., including the address header) has been changed, the analysis of the check word at the receiving terminal (as shown above) cannot reveal the occurrence of an error. It is possible to avoid this problem by using a store and forward technique. With this approach the receiving device captures and stores the entire code word, checks the address header and recognizes that it is not intended for this communicating device, changes the address, detects and/or corrects errors in the data word, recalculates the check word for the code word, and transmits the code word to the next node. This is a slow technique, especially because it has to be performed at each intervening node, and not desirable for use on high-speed data networks where each code word can be ten, hundreds, or even thousands of bits long. Also, once the data word and check word have been changed at a node, any previous errors in the data word must be detected and corrected at this node, because it is not possible to reflect these previous errors in the modified check word without additional coding, which complicates the scheme considerably. Probability theory teaches that there is a relatively low probability for errors to develop between two successive nodes, so it is inefficient to decode and recode the data and check words and detect and/or correct errors in the data word at each node.